1941. Parent
Write a program that
determines for two nodes of a tree whether the first one is a parent of
another.
Input. The first line contains the
number of vertices n (1 ≤ n ≤ 105) in a tree. The
second line contains n numbers,
the i-th one gives the vertex number of direct ancestor for the vertex i. If this value is zero, then the
vertex is a root of a tree.
The third line contains the
number of queries m (1
≤ m ≤ 105). Each of the next m lines contains two different numbers a and b (1 ≤ a, b
≤ n).
Output. For each of the m queries print on a separate line
number 1, if the vertex a is one
of the parents of a vertex b, and 0 otherwise.
|
Sample input |
Sample output |
60 1 1 2 3 354 11 43 62 6
6 5 |
0 1 1 0 0 |
SOLUTION
graphs – depth
first search
Algorithm analysis
The tree will be
stored as a directed graph, in which the edges go from ancestors to sons (to save
memory). Run depth first search on
it, compute the
timestamps d[v] and f[v] for each vertex v. Vertex a is one
of the ancestors of vertex b if d[a] < d[b] < f[b] < f[a]. It means that interval [d[b]; f[b]]
must be included in the interval [d[a]; f[a]].
But since the
inequality d[b] < f[b] is always satisfied for each vertex b, then for each input pair of vertices (query) a and b it is sufficient to check the inequalities d[a] < d[b] and f[b] < f[a].
Example
Graph given in a
sample, with timestamps, is as
follows:
For example, 1 is the
ancestor of 5, since d[1] < d[5]
è f[5] < f[1]. Indeed, the interval [7; 8] is included in [1; 12].
Algorithm realization
Since the number
of vertices in the graph is large, store the graph in an adjacency
list g. The array used is used to mark the already visited vertices. Store the
timestamps of entry and exit from the vertex in arrays d and f.
vector<vector<int> > g;
vector<int> used, d, f;
Run the function dfs of depth first search. Place the timestamps d[v] and f[v].
void
dfs(int v)
{
used[v] = 1; d[v] = time++;
for(int i = 0; i < g[v].size(); i++)
{
int to =
g[v][i];
if
(!used[to]) dfs(to);
}
f[v] = time++;
}
Function is_Parent returns 1, if a is the ancestor of b,
and 0 otherwise. Check the
fulfillment of two inequalities d[a]
< d[b] and f[b] < f[a].
int
is_Parent(int a, int
b)
{
return (d[a]
< d[b]) && (f[b] < f[a]);
}
The main part of
the program. Read the
input graph. If vertex a is the
parent of vertex i, then add a
directed edge (a, i) to the graph (to save memory, you can
use a directed graph). The vertices of the graph are numbered from 1 to n. If a = 0, then the
vertex i is a root, in
this case no edge needs to be added. In the variable root store the
number of the vertex that
is the root of the tree.
scanf("%d",&n);
g.resize(n+1);
used.resize(n+1);
d.resize(n+1);
f.resize(n+1);
for(i
= 1; i <= n; i++)
{
scanf("%d",&a);
if(!a) root =
i; else g[a].push_back(i);
}
Run the depth first search from the root of the tree root.
dfs(root);
Read the queries and print the answers to each of them in constant time.
scanf("%d",&m);
for(i
= 0; i < m; i++)
{
scanf("%d
%d",&a,&b);
printf("%d\n",is_Parent(a,b));
}